package com.zjsru.plan2023.other;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Author: CookLee
 * @Date: 2023/8/6
 *  两个最好的不重叠活动
 *  \
 *  给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，
 *  如果你参加这个活动，那么你可以得到价值 valuei 。你 最多 可以参加 两个时间不重叠 活动，使得它们的价值之和 最大 。
 *  \
 *  输入：events = [[1,3,2],[4,5,2],[2,4,3]]
 * 输出：4
 * 解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。
 * \
 * 输入：events = [[1,3,2],[4,5,2],[1,5,5]]
 * 输出：5
 * 解释：选择活动 2 ，价值和为 5 。
 */
public class MaxTwoEvents {
    
    /**
     * 排序 + 二分
     *
     * @param events 事件
     * @return int
     */
    public int maxTwoEvents(int[][] events) {
        int len = events.length;
        //按照每个事件的结束时间进行升序排序
        Arrays.sort(events, Comparator.comparingInt(e -> e[1]));
        //分别用来记录每个事件选中一次和选中二次的最大价值
        int[] f = new int[len], g = new int[len];
        for (int i = 0; i < len; i++) {
            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (events[mid][1] >= events[i][0]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            //当前事件的价值，表示当前事件被选中
            f[i] = events[i][2];
            if (right > -1) {
                g[i] = f[right] + events[i][2];
            }
            if (i > 0) {
                f[i] = Math.max(f[i], f[i - 1]);
                g[i] = Math.max(g[i], g[i - 1]);
            }
        }
        return Math.max(f[len - 1], g[len - 1]);
    }
    
    public static void main(String[] args) {
        MaxTwoEvents maxTwoEvents = new MaxTwoEvents();
        int[][] events = new int[][] {{1,3,2},{4,5,2},{2,4,3}};
        System.out.println(maxTwoEvents.maxTwoEvents(events));
    }
}
